#include <iostream>
#include <vector>
#include <list>
#include <stdlib.h>
#include <algorithm>
#include <sys/time.h>
#include <sys/resource.h>
using namespace std;

struct term_values{
    unsigned term;
    unsigned dontCare;
    bool used;
    list<unsigned> mtList;
};


class minTerm{

    public:
        term_values tv;

        term_values mtAssign(unsigned t, unsigned dc, bool u);
        unsigned termOnes(unsigned t);
        unsigned termBits(unsigned t);
        void printBin(unsigned t,unsigned mb);
        void printDash(unsigned t,unsigned d,unsigned mb);

};

term_values minTerm::mtAssign(unsigned t, unsigned dc, bool u){
    tv.term = t;
    tv.dontCare =dc;
    tv.used = u;
    return (tv);
}

unsigned minTerm::termOnes(unsigned t){
    short shiftTerm =0;
    unsigned numOnes =0;
	for(;t>0;t>>=1){
		shiftTerm = t%2;
		if(shiftTerm) {
			numOnes++;
		}
	}
	return(numOnes);
}

unsigned minTerm::termBits(unsigned t){
    unsigned numBits =0;
	for(;t>0;t>>=1){
        numBits++;
	}
	return(numBits);
}

void minTerm::printBin(unsigned t, unsigned mb) {
    int i;

	unsigned bits[mb];

	for(i=0;((t>0)||(i<mb));i++)	{
		bits[i] = t%2;
		t>>= 1;
	}
	for(int j=i-1;j>=0;j--){
		cout<<bits[j];
	}
}

void minTerm::printDash(unsigned t, unsigned d,unsigned mb) {
    int i;

    unsigned bits[mb];
	for(i=0;((t>0)||(i<mb));i++) {
		if(!(d%2)){
			bits[i] = t%2;
		}
		else {
			bits[i] = 2;
		}

		t >>= 1;
		d >>= 1;
	}
	for(int j=i-1;j>=0;j--) {
		if(bits[j]!=2)
			cout<<bits[j];
		else
			cout<<"-";
	}
}

///////////////////////////////////////////////////////////////////

struct val{
    unsigned t;
    unsigned d;
};

typedef vector<vector<term_values> > table;
class qmMethod{
    private:
        table initTable;
        table processTable;
        unsigned minBits;
        vector<unsigned> inValues;
        vector<vector<bool> > PITable;
        vector<term_values> primeImps;
        vector<val> EPI;
    public:
        friend class minTerm;

        qmMethod(minTerm& mt,int n,char* arg[]);
        void createInitTable(minTerm& mt,int n,char* arg[]);
        void printInitTable(minTerm &mt,table &T);
        void printProcTable(minTerm &mt,table &T,unsigned c);
        unsigned createProcTable(minTerm &mt,table &fromTable,table &toTable);
        void clearTable(table & T);
        void findPIs(minTerm &mt);
        void printPI(minTerm &mt);
        void createPITable();
        bool findVec(vector<term_values> & v,term_values t);
        void findEPI(minTerm &mt);
        void findDom(minTerm &mt);


};

qmMethod::qmMethod(minTerm& mt,int n,char* arg[]){
    minBits =4;
    initTable.resize(1);
    processTable.resize(1);
    primeImps.resize(1);
    createInitTable(mt,n,arg);
    findPIs(mt);
    createPITable();
    findEPI(mt);
    findDom(mt);
}

void qmMethod::createInitTable(minTerm& mt,int n,char* arg[]){
    unsigned short ones,bits;
    unsigned t;
    for(int i=0;i<(n-1);i++){
        t= unsigned(atoi(arg[i+1]));
        bits = mt.termBits(t);
        if(bits>minBits){
            minBits = bits;
        }
        ones = mt.termOnes(t);
        if(ones+1>initTable.size()){
            initTable.resize(ones+1);
        }
        term_values temp = mt.mtAssign(t,0,false);
        inValues.push_back(temp.term);
        initTable[ones].push_back(temp);
        initTable[ones].back().mtList.push_back(t);
    }
    printInitTable(mt,initTable);
}

void qmMethod::printInitTable(minTerm &mt,table &T) {            //change

    cout<<endl<<"\nINITIAL TABLE\n"<<endl;
    for(int i=0;i<T.size();i++)	{
        cout<<i;
        for(int j=0;j<T[i].size();j++) {

            cout<<"\t"<<T[i][j].mtList.back()<<"\t";
            mt.printBin(T[i][j].term,minBits);
            cout<<endl;
        }
        cout<<"\n___________________________________________\n"<<endl;
    }
}

unsigned qmMethod::createProcTable(minTerm &mt,table &fromTable,table &toTable){
    unsigned short ones;
    unsigned count=0;
	term_values tmp;
	unsigned tmp_term, tmp_dc;
	for(int x=0;x<fromTable.size()-1;x++) {
		for(int y=0;y<fromTable[x].size();y++) {
			for(int z=0;z<fromTable[x+1].size();z++) {
				if(fromTable[x][y].dontCare == fromTable[x+1][z].dontCare) {
					tmp_term = fromTable[x][y].term & fromTable[x+1][z].term;
					tmp_dc   = fromTable[x][y].term ^ fromTable[x+1][z].term;

					if(mt.termOnes(tmp_dc)==1) {
					    count++;
						tmp_dc^= fromTable[x][y].dontCare;

						fromTable[x][y].used   = true;
						fromTable[x+1][z].used = true;

						ones = mt.termOnes(tmp_term);

						if(ones+1>toTable.size()){
							toTable.resize(ones+1);
						}
						tmp = mt.mtAssign(tmp_term, tmp_dc, false);
						toTable[ones].push_back(tmp);
						toTable[ones].back().mtList.insert(toTable[ones].back().mtList.end(),fromTable[x][y].mtList.begin(), fromTable[x][y].mtList.end());
                        toTable[ones].back().mtList.insert(toTable[ones].back().mtList.end(),fromTable[x+1][z].mtList.begin(), fromTable[x+1][z].mtList.end());
					}
				}
			}
		}
	}
	clearTable(fromTable);
	return(count);
}

void qmMethod::printProcTable(minTerm &mt,table &T,unsigned c) {            //change

    if(T.size()!=1){
        cout<<endl<<"PROCESS TABLE "<<c<<"\n"<<endl;
        for(int i=0;i<T.size();i++)	{
            cout<<i;
            for(int j=0;j<T[i].size();j++) {
                cout<<"\t";
                for(list<unsigned>::iterator it= T[i][j].mtList.begin() ; it != T[i][j].mtList.end() ; it++){
                    cout<<*it<<" ";
                }
                cout<<"\t";
                mt.printDash(T[i][j].term,T[i][j].dontCare,minBits);
                cout<<endl;
            }
            cout<<"\n___________________________________________\n"<<endl;
        }
    }
}

void qmMethod::clearTable(table & T){
    for (int i=0;i<T.size();i++){
        for (int j=0;j<T[i].size();j++){
            if (T[i][j].used == false){
                        if(!findVec(primeImps,T[i][j])){
                            primeImps.push_back(T[i][j]);
                    }
            }
        }
    }
    T.clear();
    T.resize(1);
}

bool qmMethod::findVec(vector<term_values> & v,term_values t){
    bool match;
    for(int i=0;i<v.size();i++){
        if (t.dontCare==v[i].dontCare && t.term == v[i].term){
            match =1;
        }
    }
    return(match);
}

void qmMethod::findPIs(minTerm &mt){
    int i=1;
    unsigned count = createProcTable(mt,initTable,processTable);
    printProcTable(mt,processTable,1);
    while ( count!=0){
        if (i%2!=0){
           i++;
           count = createProcTable(mt,processTable,initTable);
           printProcTable(mt,initTable,i);

        }
        else {
            i++;
            count = createProcTable(mt,initTable,processTable);
            printProcTable(mt,processTable,i);

        }
    }
    printPI(mt);
}

void qmMethod::printPI(minTerm &mt){
    list<unsigned>::iterator it;
    cout<<"\nPRIME IMPLICANTS\n"<<endl;
    for(int i=1;i<primeImps.size();i++){
        for(it= primeImps[i].mtList.begin() ; it != primeImps[i].mtList.end() ; it++){
            cout<<*it<<" ";
        }
        cout<<"\t";
        mt.printDash(primeImps[i].term,primeImps[i].dontCare,minBits);
        cout<<endl;
    }
}

void qmMethod::createPITable(){
    int index;

    vector<unsigned >::iterator it;
    PITable.resize(inValues.size(), vector<bool> (primeImps.size()-1,0));
    for(int i=1;i<primeImps.size();i++){
        for(list<unsigned>::iterator lit= primeImps[i].mtList.begin();lit!=primeImps[i].mtList.end();lit++){
            it = find(inValues.begin(),inValues.end(),*lit);
            index=it-inValues.begin();
            PITable[index][i-1] = 1;
        }
    }
//Printing PI Table: for verification
//        for(int i=0;i<PITable.size();i++){
//        for(int j=0;j<PITable[i].size();j++){
//            cout<<PITable[i][j]<<" ";
//        }
//        cout<<endl;
//    } cout<<endl;
}

void qmMethod::findEPI(minTerm &mt){
    int rowsum=0;
    int rsum[PITable.size()];
    val tmp;
    for(int i=0;i<PITable.size();i++){
        for(int j=0;j<PITable[i].size();j++){
            rowsum=rowsum+PITable[i][j];
        }
        rsum[i]=rowsum;
        rowsum=0;
    }
    for(int i=0;i<PITable.size();i++){
        if(rsum[i]==1){
            for(int j=0;j<PITable[i].size();j++){
                if(PITable[i][j]==1){
                    PITable[i][j]=0;
                    tmp.t = primeImps[j+1].term;
                    tmp.d = primeImps[j+1].dontCare;
                    EPI.push_back(tmp);
                    for(int k=0;k<PITable.size();k++){
                        if(PITable[k][j]==1){
                            PITable[k][j]=0;
                            for(int l=0;l<PITable[k].size();l++){
                                PITable[k][l]=0;
                            }
                        }
                    }
                }
            }
        }
    }
//Printing PI Table: for verification
//    for(int i=0;i<PITable.size();i++){
//        for(int j=0;j<PITable[i].size();j++){
//            cout<<PITable[i][j]<<" ";
//        }
//        cout<<endl;
//    }
//        for(int i=0;i<EPI.size();i++){
//        mt.printDash(EPI[i].t,EPI[i].d,minBits);
//        cout<<endl;
//    }
}


void qmMethod::findDom(minTerm &mt){
    int coland=0; int col1=0; int col2=0; int color=0;
    val tmp;
    for(int i=0;i<primeImps.size()-1;i++){
        for(int j=0;j<primeImps.size()-1;j++){
            for(int l=0;l<primeImps.size()-1;l++){
                if(i!=j && j!=l && i!=l){
                    for(int k=0;k<inValues.size();k++){
                        col1=col1+PITable[k][i];
                        col2=col2+PITable[k][j];
                        coland=coland+(PITable[k][i]&PITable[k][j]);
                        color=color+((PITable[k][j]|PITable[k][l])&PITable[k][i]);
                    }
                    if(coland==col1 && coland!=0){
                        for(int k=0;k<inValues.size();k++){
                            PITable[k][i]=0;
                        }
                    }
                    else if(coland==col2&& coland!=0){
                        for(int k=0;k<inValues.size();k++){
                            PITable[k][j]=0;
                        }
                    }
                    if(color==col1 && color!=0){
                        for(int k=0;k<inValues.size();k++){
                            PITable[k][i]=0;
                        }
                    }
                    col1=0;
                    col2=0;
                    coland=0;
                    color=0;
                }
            }
        }
    }

//Printing PI Table: for verification
//    cout<<endl;
//        for(int i=0;i<PITable.size();i++){
//        for(int j=0;j<PITable[i].size();j++){
//            cout<<PITable[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    for(int i=0;i<primeImps.size()-1;i++){
        for(int j=0;j<inValues.size();j++){
            col1=col1+PITable[j][i];
        }
        if(col1!=0){
            tmp.t=primeImps[i+1].term;
            tmp.d=primeImps[i+1].dontCare;
            EPI.push_back(tmp);
        }
        col1=0;
    }

    cout<<"\nMINIMUM COVER FOR THE GIVEN FUNCTION\n"<<endl;
    for(int i=0;i<EPI.size();i++){
        mt.printDash(EPI[i].t,EPI[i].d,minBits);
        cout<<endl;
    }
}

double getcputime(void){

    struct timeval tim;
    struct rusage ru;

    getrusage(RUSAGE_SELF, &ru);
    tim=ru.ru_utime;
    double t=(double)tim.tv_sec + (double)tim.tv_usec / 1000000.0;
    tim=ru.ru_stime;
    t+=(double)tim.tv_sec + (double)tim.tv_usec / 1000000.0;

    return t;
}

int main(int argc, char *argv[]){

    minTerm mt;
    qmMethod qm(mt,argc,argv);

    double cputime = getcputime();
    cout<<"\nCPU Time:"<<cputime<<"s"<<endl;

    return(0);
}



